package 每日一题.array.二维数组中查找;

/**
 * @author 标记
 * @date 2021/1/29
 */
public class Solution {

    /**
     * Q:二维数组中查找数组
     *      [1,2,8,9]
     *      [2,4,9,12]
     *      [4,7,10,13]
     *      [6,8,11,15]
     * [例子：]
     *      输入 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
     *      输出 true
     * @param args
     */
    public static void main(String[] args) {
        int[][] array = {};
        boolean b = findCheckout(111, array);
        System.out.println(b);
    }

    /**
     * 动态规划？
     * @param target
     * @param array
     * @return
     */
    public static boolean findCheckout(int target,int[][] array) {

        int rows = array.length;
        int cols = array[0].length;
        if (rows==0) {
            return false;
        }
        if (cols==0) {
            return false;
        }

        int row = 0;
        int col = cols-1;
        int num = array[row][col];
        //循环次数不确定
        while (col>=0&&row<rows) {
            if (num<target) {
                col--;
            } else if (num>target) {
                row++;
            } else {
                return true;
            }
        }

        return false;
    }

    /**
     * 暴力解法
     * @param target
     * @param array
     * @return
     */
    public static boolean find(int target,int[][] array) {

        for (int i = 0; i < array.length ; i++) {
            for (int j = 0; j < array[0].length ; j++) {
                if (array[i][j]==target) {
                    return true;
                }
            }
        }

        return false;
    }
}
